Skip to main content

04 值迭代与策略迭代

04 值迭代与策略迭代​

值迭代算法​

值迭代算法包含策略更新（policy update）和值更新（value update）两部分。具体流程如下：

  • 猜测初始值v0v_0
  • 如果∣∣vk−vk−1∣∣||v_k - v_{k - 1}||小于threshold，停止迭代
    • 遍历所有ss、aa，求出qk(s,a)q_k(s,a)
    • 求出qkq_k后，得到对应的a∗a^*（策略更新，实际上隐式更新了策略）
    • vk+1(s)=max qk(a,s)v_{k + 1}(s) = max~q_k(a,s)（值更新）

策略迭代算法​

值迭代算法以猜测的状态值作为初始值，而策略迭代算法以随机策略作为初始值。策略迭代算法分为策略评估（policy evaluation，PE）和策略提升（policy improvement，PI）两部分。

  • PE：根据猜测策略和贝尔曼公式，求解出状态价值。
  • PI：根据已有的状态价值，通过BOE求出新的最大化策略。

具体流程：

  • 猜测初始值π0\pi_0
  • 迭代：
    • PE：
      • 猜测状态价值vπk(0)v_{\pi_k}^{(0)}
      • 迭代求vv，得到收敛vπk(j+1)v_{\pi_k}^{(j + 1)}
    • PI：
      • 求出qπk(s,a)q_{\pi_k}(s,a)
      • 求出对应a∗a^*
      • 更新策略

策略迭代算法的特点是，接近目标的策略会先变好，原理目标的策略后变好。直观上的原因只有某个状态的路径上的状态都能达到目标区域，这个状态才能达到目标区域。

截断策略迭代算法​

截断策略迭代算法是值迭代和策略迭代的一般化推广。

对比值迭代和策略迭代，如果不考虑策略迭代猜测状态的那一步，则两者都是从猜测一个状态价值v0v_0开始；区别是，值迭代算法直接应用v0v_0进而求出策略、迭代到v1v_1，而策略迭代算法将v0v_0迭代（近似）无穷多次得到vπ1v_{\pi_1}。也就是说，区别就在与vv的迭代次数：值迭代是一次，策略迭代是无穷次。如果去中间值，进行有限次迭代，就得到了截断策略迭代算法。

具体流程：

  • 猜测初始值π0\pi_0
  • 迭代：
    • PE：
      • 猜测状态价值vπk(0)v_{\pi_k}^{(0)}
      • 迭代一定次数求vv，得到收敛vπk(j+1)v_{\pi_k}^{(j + 1)}
    • PI：
      • 求出qπk(s,a)q_{\pi_k}(s,a)
      • 求出对应a∗a^*
      • 更新策略

可以看到，和策略迭代的唯一区别就是通过迭代次数（而不是threshold）判断vv的迭代是否完成。

值迭代和策略迭代分别是（对vv）迭代1次和无穷次的两种特殊截断策略迭代算法。由于值迭代每次只用迭代1次的vv，策略迭代使用vπv_\pi，而截断策略迭代会迭代jj次，所以在相同的（总）迭代次数下，收敛速度有值迭代 < 截断策略迭代 < 策略迭代。